W razie problemów technicznych ze Szkopułem, prosimy o kontakt mailowy pod adresem [email protected].
Jeśli chciałbyś porozmawiać o zadaniach, rozwiązaniach lub problemach technicznych, zapraszamy na serwery Discord. Są one moderowane przez społeczność, ale członkowie zespołu technicznego też są tam aktywni.
Dwaj gracze, i , grają w grę na kwadratowej planszy o rozmiarach . Pola planszy dzielą się na białe i czarne. Gra toczy się jedynie na białych polach. Każdy gracz ma swojego piona, początkowo ustawionego na polu startowym danego gracza - jednym z białych pól planszy. Pola startowe graczy i są różne.
W każdym ruchu gracz porusza swojego piona na jedno z sąsiadujących z jego pozycją białych pól (w górę, dół, lewo lub prawo). Jeśli gracz przesunie piona na pole zajmowane w tej samej chwili przez piona przeciwnika, otrzymuje dodatkowy ruch (w ten sposób przeskakuje nad pionem przeciwnika). Zauważ, że w takim przypadku kierunek drugiego ruchu może być różny od kierunku pierwszego ruchu.
Gracze poruszają się na zmianę, pierwszy ruch wykonuje gracz . Celem gry jest dojście własnym pionem do pola startowego przeciwnika. Gracz, który dokona tego wcześniej, wygrywa. W przypadku, gdy ruch gracza składa się z dwóch posunięć i jedynie przechodzi on przez pole startowe przeciwnika (w sytuacji, gdy przeciwnik stoi na swoim polu startowym), gracz również wygrywa. Dla danej sytuacji chcemy stwierdzić, który z graczy ma strategię wygrywającą (mówi się, że gracz ma strategię wygrywającą, jeśli może on wygrać grę niezależnie od ruchów przeciwnika).
Rysunek 1. Jeśli poruszy się trzykrotnie w prawo w swoich trzech pierwszych ruchach, odpowie na każdy ruch posunięciem w górę. Dlatego, w trzecim ruchu gracz wejdzie na pole zajmowane przez piona gracza i będzie mógł ruszyć się ponownie. Z tego powodu, wcześniej osiągnie pole startowe gracza i wygra.
Rysunek 2. może zacząć od ruchów w prawo i w dół. Później, zależnie od ruchów gracza , pójdzie albo w dół, albo w prawo tak, aby uniknąć spotkania pionów. W ten sposób szybciej dotrze do pola startowego , wygrywając grę. Dlatego też ma strategię wygrywającą w tym przypadku.
Napisz program, który:
Pierwszy wiersz wejścia zawiera jedną liczbę całkowitą , oznaczającą liczbę przypadków testowych do rozpatrzenia (). Po nim następuje kolejno opisów poszczególnych testów. Każdy z testów jest opisany w następujący sposób. Pierwszy wiersz zawiera jedną liczbę całkowitą (), oznaczającą długość boku planszy. Kolejnych wierszy zawiera opis planszy. Każdy z nich składa się z znaków (bez odstępów pomiędzy nimi). Każdy ze znaków to: '.' (białe pole) '#' (czarne pole), 'A' (pozycja startowa gracza ) lub 'B' (pozycja startowa gracza ).
Możesz założyć, że istnieje ścieżka składająca się z białych pól, łącząca punkty startowe graczy i .
Dodatkowo, w testach wartych 60% punktów, , zaś w testach wartych 40% punktów, .
Dla każdego zestawu testowego na wyjściu powinien znaleźć się dokładnie jeden wiersz zawierający pojedynczy znak 'A' lub 'B', oznaczający gracza, który posiada strategię wygrywającą.
Dla danych wejściowych:
2 4 A... .#.. .... ...B 4 A... .... ..#. ...B
poprawną odpowiedzią jest:
B A
Autor zadania: Jimmy Mårdell.